1. Field of the Invention
The present invention relates to a flash memory controller for evenly using the blocks of a flash memory and the method thereof.
2. Descriptions of the Related Art
Portable memory apparatuses, such as SD/MMC, CF, MS, XD cards, are widely applied in many applications. FIG. 1 illustrates the conventional block diagram of a memory apparatus. The memory apparatus 10 includes a memory controller 11 and a non-volatile flash memory 12. The memory controller 11 includes an interface logic 110 for interfacing the data with a host (not shown), a volatile buffer memory 112 for temporarily storing the data being written to or read from the non-volatile flash memory 12, a control logic 114 and a microprocessor 116. These circuit units 110, 112, 114 and 116 are interconnected and under the control of the microprocessor 116. The non-volatile flash memory 12 includes several units (denoted as the block) and blocks with data (denoted as the written block) that cannot directly be over-written without being erased first. In other words, only an empty block can be written.
However, each block of the flash memory 12 can only be erased a certain number of times, known as the endurance times. For example, one block may only be erased ten thousands times before the block is unavailable for further erasing. As a result, the block is no longer working. When the flash memory 12 has a failed block, it may only be read or malfunction, regardless whether or not there are any other good blocks. Generally, the number of times a block of a single-level-cell flash memory can be erased one hundred thousand times and that of a multi-level-cell flash memory is only ten thousand erase times.
FIG. 2 illustrates a lookup table for linking the logical address to the physical address. The linking table 20 may be stored in the buffer memory 112 or in the control logic 114. The linking table 20 represents the relationship between the logical address transmitted from the host and the physical address of each block of the flash memory 12. The table 20 may include the erase count corresponding to each block of the flash memory 12. The erased count represents the number of times the block has been erased or reprogrammed. Initially, the erased count corresponding to each of the blocks is zero.
FIG. 3A˜3D illustrate examples of the conventional wear-leveling. In FIG. 3A, it is assumed that the flash memory 12 has data in block 0, block 1, block 2, block 3 and block 4, and a new data that is yet to be programmed or written into the flash memory 12 to replace the old data in block 1. The block 1 should be firstly erased. The erase count corresponding to the block 1 is increased by one and then new data is programmed into the block 1. As shown in FIG. 3B, data stored in the block 1 of the flash memory 12 is changed and the erase count corresponding to the block 1 is “1” now. As shown in FIG. 3C, it is understood that the erase counts corresponding to the frequently used blocks should be a large number after the flash memory 12 is reprogrammed/accessed for a long time. It has been found that the erase count corresponding to block 0 is 500, the erase count corresponding to block 1 is 1000, erase count corresponding to block 2 is 360, erase count corresponding to block 3 is 410, erase count corresponding to block 4 is 230, etc. The erase count corresponding to block 1 is a large mount because data stored in the block 1 is usually updated. The large mount also means that the data in the block 1 is hot data. Once the new data corresponds to the logical address (LA1) programmed into the block 1 again and the erased count reaches a predetermined value, for example 1000, the un-frequently used block 4 with cold data may be selected by searching for the lowest erased count to swap with the block 1. First, the cold data in the un-frequently used block 4 is first read from the block 4, temporarily stored in the buffer memory 112 and re-programmed into the block 1 after the block 1 is erased. Second, the new data is programmed into block 4 after it is also erased. Third, the relationship between LA 1, LA4, block 0 and block 4 is re-linked in the lookup table 20 as shown in FIG. 3D. It is noted that the erase count corresponding to the block 1 and block 4 are also increased by one after the swapping. By doing so, the hot data corresponding to LA 1 will be directed and programmed into the block 4 with a smaller erase count, which prevents the block 1 from malfunctioning or failing.
However, the conventional wear-leveling described above has several disadvantages. First, all of the erase counts are absolute values that need a mount of bit counts to record in the buffer memory 112 when operating the wear-leveling and to also occupy the capacity of the flash memory 12 when “blank” is recorded back into the flash memory 12. Second, comparing and searching for the block with a smaller number of erase counts impacts the performance greatly. Third, it costs one more erase count corresponding to the block with the least number of erase counts, i.e. block 4. Most importantly, conventional wear-leveling is a rough methodology that can not fully utilize every one of the blocks.
Therefore, the memory industry needs a way to manage the use of blocks and to utilize the blocks more evenly, fully, efficiently and at a low cost.